package main

import "strconv"

const SEG_CNT = 4

func restoreIpAddresses(s string) []string {
	var segments [SEG_CNT]int
	var res []string

	var dfs func(segId, start int)
	dfs = func(segId, start int) {
		//* 4段IP都已计算
		if segId == SEG_CNT {
			if start == len(s) { // 连结成字符串
				ipAddr := ""
				for i := 0; i < SEG_CNT; i++ {
					ipAddr += strconv.Itoa(segments[i])
					if i != SEG_CNT-1 {
						ipAddr += "."
					}
				}
				res = append(res, ipAddr)
			}
			return
		}

		//* 还未找到四段IP，但是已经遍历完了字符串
		if start == len(s) {
			return
		}

		//* 由于不能有前导〇，如果当前数字为〇，那么当前段IP只能为〇
		if s[start] == '0' {
			segments[segId] = 0
			dfs(segId+1, start+1)
		}

		//* 一般情况 (有 0 也可以进来)
		addr := 0
		for end:=start; end<len(s); end++ {
			addr = addr*10 + int(s[end] - '0')
			if addr > 0 && addr <= 0xFF {
				segments[segId] = addr
				dfs(segId+1, end+1)
			} else {
				break // 杜绝前导〇和超出255的情况
			}
		}
	}

	dfs(0, 0)
	return res
}

// func dfs(s string, segId, start int) {
// }
